#include "searchengine.h"

SearchEngine::SearchEngine()
{

}

SearchEngine::~SearchEngine()
{

}

Move SearchEngine::SearchAGoodMove( Byte matrix[15][15], long color )
{
    Move best;

    FailsoftAlphabeta(matrix, color, 2, best, -20000, 20000);

    return best;
}

long SearchEngine::Negamax( Byte matrix[15][15], long color, long depth, 
                           Move& best_move )
{
    // if depth is 0 return the value of current node
    Evalutor evalutor;
    if (0 == depth) {
        return evalutor.Evaluate(matrix, static_cast<ChessType>(color));
    }

    // generate possible moves of current node
    MoveGenerator move_generator;
    MoveList list = move_generator.GeneratePossibleMove(matrix, color);

    // the opposite color
    long opposite_color = color == 1 ? 2 : 1;

    // set best score to negative infinity
    long best_score = -10000;
    best_move.x = list[0].x;
    best_move.y = list[0].y;

    for (MoveList::iterator i = list.begin(); i != list.end(); i++) {
        // make move
        AIMove& move = *i;
        MakeMove(matrix, move);

        // select the max score of current ply
        Move m;
        move.score = -Negamax(matrix, opposite_color, depth - 1, m);
        if (move.score > best_score) {
            best_score = move.score;
            best_move.x = move.x;
            best_move.y = move.y;
        }

        // unmake move
        UnmakeMove(matrix, move);
    }

    // if game over, return value of current node
    long value = evalutor.Evaluate(matrix, static_cast<ChessType>(color));
    if ( value > 8000 || value < -8000) {
        return value;
    }

    // return the best score
    return best_score;
}

long SearchEngine::NegamaxAlphabeta( Byte matrix[15][15], long color, long depth, 
                            Move& best_move, long alpha, long beta )
{
    Evalutor evalutor;
    if (0 == depth) {
        return evalutor.Evaluate(matrix, static_cast<ChessType>(color));
    }

    MoveGenerator move_generator;
    MoveList list = move_generator.GeneratePossibleMove(matrix, color);

    long opposite_color = color == 1 ? 2 : 1;

    best_move.x = list[0].x;
    best_move.y = list[0].y;

    for (MoveList::iterator i = list.begin(); i != list.end(); i++) {
        AIMove& move = *i;
        MakeMove(matrix, move);

        Move m;

        move.score = -NegamaxAlphabeta(matrix, opposite_color, depth - 1, m, -beta, -alpha);

        UnmakeMove(matrix, move);

        if (move.score > alpha) {
            alpha = move.score;
            best_move.x = move.x;
            best_move.y = move.y;
        }
        if (alpha >= beta) break;
    }

    long value = evalutor.Evaluate(matrix, static_cast<ChessType>(color));
    if ( value > 8000 || value < -8000) {
        return value;
    }

    return alpha;
}

long SearchEngine::FailsoftAlphabeta( Byte matrix[15][15], long color, long depth, Move& best_move, long alpha, long beta )
{
    Evalutor evalutor;
    if (0 == depth) {
        return evalutor.Evaluate(matrix, static_cast<ChessType>(color));
    }

    MoveGenerator move_generator;
    MoveList list = move_generator.GeneratePossibleMove(matrix, color);

    long opposite_color = color == 1 ? 2 : 1;

    long best_score = -20000;
    best_move.x = list[0].x;
    best_move.y = list[0].y;

    for (MoveList::iterator i = list.begin(); i != list.end(); i++) {
        AIMove& move = *i;
        MakeMove(matrix, move);
        Move m;
        move.score = -FailsoftAlphabeta(matrix, opposite_color, depth - 1, m, -beta, -alpha);
        UnmakeMove(matrix, move);

        if (move.score > best_score) {
            best_score = move.score;
            best_move.x = move.x;
            best_move.y = move.y;
            if (move.score >= alpha)
                alpha = move.score;
            if (move.score >= beta)
                break;
        }
    }

    long value = evalutor.Evaluate(matrix, static_cast<ChessType>(color));
    if ( value > 8000 || value < -8000) {
        return value;
    }

    return best_score;
}